#define _CRT_SECURE_NO_WARNINGS 1

void PrevOrder(int* ret, struct TreeNode* root, int* size)
{
    if (root == NULL)
    {
        return;
    }
    PrevOrder(ret, root->left, size);
    PrevOrder(ret, root->right, size);
    ret[(*size)++] = root->val;
}


int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    int* ret = (int*)malloc(sizeof(int) * 1000);
    *returnSize = 0;
    PrevOrder(ret, root, returnSize);

    return ret;
}

void InOrder(int* ret, struct TreeNode* root, int* size)
{
    if (root == NULL)
    {
        return;
    }
    InOrder(ret, root->left, size);
    ret[(*size)++] = root->val;
    InOrder(ret, root->right, size);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    int* ret = (int*)malloc(sizeof(int) * 1000);
    *returnSize = 0;
    InOrder(ret, root, returnSize);

    return ret;
}

bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2)
{
    if (root1 == NULL && root2)
        return false;
    if (root2 == NULL && root1)
        return false;
    if (root1 == NULL && root2 == NULL)
        return true;
    if (root1->val == root2->val)
        return _isSymmetric(root1->left, root2->right)
        && _isSymmetric(root1->right, root2->left);
    return false;
}

bool isSymmetric(struct TreeNode* root) {
    if (root == NULL)
    {
        return true;
    }
    return _isSymmetric(root->left, root->right);
}

int height(struct TreeNode* root)
{
    if (root == NULL)
        return 0;
    return fmax(height(root->left), height(root->right)) + 1;
}

bool isBalanced(struct TreeNode* root) {
    if (root == NULL)
        return true;
    return fabs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}